//
// Created by rebeater on 7/20/21.
//

#ifndef LEETCODE__TREE_H_
#define LEETCODE__TREE_H_
#include <vector>
using namespace std;
template<typename T>
class BinaryTree {
 public:
  T value{};
  BinaryTree<T> *left = nullptr;
  BinaryTree<T> *right = nullptr;

 public:
  explicit BinaryTree(vector<T> &values) : BinaryTree(values, 0) {}
 public:
  /*遍历*/
  vector<T> ToPreOrder();
  vector<T> ToInOrder();
  vector<T> ToPostOrder();
  vector<T> ToLayerOrder();
  /*深度*/
  int Depth();
 private:
  void ToPreOrder(vector<T> &res);
  void ToInOrder(vector<T> &res);
  void ToPostOrder(vector<T> &res);
  void ToLayerOrder(vector<T> &res);
  BinaryTree(vector<T> values, int index) {
	value = values[index];
	left = nullptr;
	right = nullptr;
	if (index * 2 + 1 < values.size()) {
	  left = new BinaryTree(values, index * 2 + 1);
	}
	if (index * 2 + 2 < values.size()) {
	  right = new BinaryTree(values, index * 2 + 2);
	}
  }
 public:
  ~BinaryTree();
};

template<typename T>
vector<T> BinaryTree<T>::ToPreOrder() {
  vector<T> res;
  this->ToPreOrder(res);
  return res;
}
template<typename T>
vector<T> BinaryTree<T>::ToPostOrder() {
  vector<T> res;
  this->ToPostOrder(res);
  return res;
}
template<class T>
vector<T> BinaryTree<T>::ToInOrder() {
  vector<T> res;
  this->ToInOrder(res);
  return res;
}
/**
 * 先根遍历
 * @tparam T
 * @param res
 */
template<class T>
void BinaryTree<T>::ToPreOrder(vector<T> &res) {
  res.emplace_back(value);
  if (left != nullptr)
	this->left->ToPreOrder(res);
  if (right != nullptr) {
	this->right->ToPreOrder(res);
  }
}
template<typename T>
void BinaryTree<T>::ToPostOrder(vector<T> &res) {
  if (this->left != nullptr) {
	this->left->ToPostOrder(res);
  }
  if (this->right != nullptr) {
	this->right->ToPostOrder(res);
  }
  res.push_back(value);
}

template<typename T>
void BinaryTree<T>::ToInOrder(vector<T> &res) {
  if (this->left != nullptr) {
	this->left->ToPostOrder(res);
  }
  res.push_back(value);
  if (this->right != nullptr) {
	this->right->ToPostOrder(res);
  }
}
template<typename T>
vector<T> BinaryTree<T>::ToLayerOrder() {
  vector<T> res;
  ToLayerOrder(res);
  return res;
}

#include <queue>

/**
 * 二叉树层次遍历，实际上类似于广度优先搜索
 * @tparam T
 * @param res
 */
template<typename T>
void BinaryTree<T>::ToLayerOrder(vector<T> &res) {
  queue<BinaryTree<T> *> que;
  que.push(this);
  BinaryTree<T> *top;
  while (!que.empty()) {
	top = que.front();
	res.push_back(top->value);
	que.pop();
	if (top->left != nullptr) {
	  que.push(top->left);
	}
	if (top->right != nullptr) {
	  que.push(top->right);
	}
  }
}

template<typename T>
int BinaryTree<T>::Depth() {
  int ll = 0, rl = 0;
  if (this->left != nullptr) {
	ll = this->left->Depth();
  }
  if (this->right != nullptr) {
	rl = this->right->Depth();
  }
  return ll > rl ? (ll + 1) : (rl + 1);
}
template<typename T>
BinaryTree<T>::~BinaryTree() {
  if (this->left != nullptr) {
	delete (this->left);
  }
  if (this->right != nullptr) {
	delete this->right;
  }
}

#endif //LEETCODE__TREE_H_
